//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 
//
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：[3,2,3]
//输出：3 
//
// 示例 2： 
//
// 
//输入：[2,2,1,1,1,2,2]
//输出：2
// 
//
// 
//
// 进阶： 
//
// 
// 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 
// 
// Related Topics 数组 哈希表 分治 计数 排序 👍 1132 👎 0


package Array;

import java.util.Arrays;
import java.util.HashMap;

//leetcode submit region begin(Prohibit modification and deletion)
class majorityElement {
    public  int majorityElement(int[] nums) {
        //        摩尔投票法思路,候选人(cand_num)初始化为nums[0]，票数count初始化为1。
//当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
//当票数count为0时，更换候选人，并将票数count重置为1。
//遍历完数组后，cand_num即为最终答案。
//
        int len = nums.length;
        if(len==1){
            return nums[0];
        }
        //多数元素，投票算法
        int count = 1;
        int canditate = nums[0];
        for(int i=1;i<len;i++){
            if(canditate == nums[i]){
                count++;
            }else{
                count--;
                if(count==0){
                    //换人
                    canditate = nums[i];
                    count = 1;
                }
            }
        }
        return canditate;
    }
    
    public  int majorityElement2(int[] nums) {
        //        数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    public  int majorityElement1(int[] nums) {
        /*
        哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)。
         */
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if (map.containsKey(key)) {
                int value = map.get(key) + 1;
                map.put(key, value);
            } else {
                map.put(key, 0);
            }
        }
        int res = 0;
        for (Integer integer : map.keySet()) {
            if (map.get(integer) >= nums.length / 2) {
                res = integer;
            }
        }

        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
